Sudan function

In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function. The Sudan function was the first function having this property to be published.

It was discovered in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert. It was published in^[1].

Definition

$F _0 (x, y) = x%2By,\,$

$F _{n%2B1} (x, 0) = x, \ n \ge 0\,$

$F _{n%2B1} (x, y%2B1) = F _n (F_{n%2B1} (x, y), F_{n%2B1} (x, y) %2B y %2B 1), \ n\ge 0.\,$

Value Tables

Values of F₁(x, y)
y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	3	5	7	9	11
2	4	8	12	16	20	24
3	11	19	27	35	43	51
4	26	42	58	74	90	106
5	57	89	121	153	185	217
6	120	184	248	312	376	440

In general, F₁(x, y) is equal to F₁(0, y) + 2^y x.

Values of F₂(x, y)
y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	8	27	74	185	440
2	19	F₁(8, 10) = 10228	F₁(27, 29) ≈ 1.55 ×10¹⁰	F₁(74, 76) ≈ 5.74 ×10²⁴	F₁(185, 187) ≈ 3.67 ×10⁵⁸	F₁(440, 442) ≈ 5.02 ×10¹³⁵

References

Cristian Calude, Solomon Marcus, Ionel Tevy, The first example of a recursive function which is not primitive recursive, Historia Mathematica 6 (1979), no. 4, 380–384 doi:10.1016/0315-0860(79)90024-7

^ Bull. Math. Soc. Roumaine Sci. 30 (1927), 11 - 30; Jbuch 53, 171

‹The stub template below has been proposed for renaming to . See stub types for deletion to help reach a consensus on what to do.
Feel free to edit the template, but the template must not be blanked, and this notice must not be removed, until the discussion is closed. For more information, read the guide to deletion.›

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	3	5	7	9	11
2	4	8	12	16	20	24
3	11	19	27	35	43	51
4	26	42	58	74	90	106
5	57	89	121	153	185	217
6	120	184	248	312	376	440

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	3	5	7	9	11
2	4	8	12	16	20	24
3	11	19	27	35	43	51
4	26	42	58	74	90	106
5	57	89	121	153	185	217
6	120	184	248	312	376	440

y\x	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	3	5	7	9	11
2	4	8	12	16	20	24
3	11	19	27	35	43	51
4	26	42	58	74	90	106
5	57	89	121	153	185	217
6	120	184	248	312	376	440